package sort;

import java.util.Arrays;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/9
 */
public class Quick {
    public static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);//基准点的索引值

        quick(a,l,p-1);//左边分区范围
        quick(a,p+1,h);
    }
    private static int partition(int[] a, int l, int h) {
        //返回值代表了基准点所在的正确索引,用它确定下一轮分区的边界
        //l和h都表示数组的索引

        int pv = a[h];

        int i = l;

        //如果j找到小于基准点的元素,则和i元素交换位置,并且i的索引++
        for (int j = l; j < h ; j++) {
            if (a[j] < pv) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
            }
        }

        //交换完之后基准点归位,i就是基准点正确的位置
        int temp = a[h];
        a[h] = a[i];
        a[i] = temp;
        System.out.println(Arrays.toString(a));
        return i;
    }
}
